COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00017 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a01.tex[bkg,phy] \today\hfill}

\bigskip
\ctrline{\bf Stratified Sampling on Squares and Cubes}
\ctrline{Robert W. Floyd}
\ctrline{(A Working Note)}

\bigskip
Given a square array of numbers, $U↓{ij}$, $i,j\in(1$ . . $N)$, I~estimate
the sum over the array by sampling once in each row and column and
summing. This sum, for example, can be multiplied by $N$ to get an unbiased
estimate for $\sum↓{i,j}U↓{ij}$, or divided by~$N$ to get an unbiased
estimate for the average of~$U↓{ij}$. We can think of the samples as
$\{\,U↓{p(i),q(i)}\mid i\in(1,N)\,\}$, or as
$\{\,U↓{i,p(i)}\mid i\in(1,N)\,\}$, for $p$ and~$q$ random permutations
on~1,~$N$.

Each possible sample gives a linear combination of values of~$U$, so the
variance of the sample sum must be a quadratic form $\sum U↓{ab}U↓{de}W↓{abde}$,
where the symmetries of the sampling imply numerous symmetries of~$W$.
In fact, the values of $W↓{1111}$, $W↓{1112}$, and $W↓{1122}$ imply all
other values, so there are only three degrees of freedom.

Let $U↓{a\ast}=\sum↓jU↓{aj}$, 
$U↓{\ast b}=\sum↓iU↓{ib}$, 
$U↓{\ast \ast}=\sum↓{i,j}U↓{ij}$. Three quadratic forms over $U$ which have
the right symmetries and are linearly independent for $N≥2$ are:
$$\eqalign{T↓0&=\sum U↓{ab}↑2\cr
T↓1&=\sum U↓{a\ast}↑2+\sum U↓{\ast b}↑2\cr
T↓2&=U↓{\ast\ast}↑2\cr}$$
where by convention we sum over all subscripts. Then the variance must
have the form of a linear combination of $T↓0$, $T↓1$, and~$T↓2$.
By consideration of some special cases, we determine the proper combination
of $T↓0$, $T↓1$, and~$T↓2$. Let $F↓i$ be the case where $U$ is~1 on a
subset of dimension~$i$, 0~elsewhere.
$$\vcenter{\halign{$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\lft{#}$\qquad&
$\ctr{#}$\qquad&$\lft{#}$\cr
\hbox{Case}&V&T↓0&T↓1&T↓2\cr
\noalign{\smallskip}
F↓0&{N-1\over N↑2}&1&2&1\cr
F↓1&0&N&N↑2+N&N↑2\cr
F↓2&0&N↑2&2N↑3&N↑4\cr}}$$
By standard methods, we find
$$V={1\over N↑2(N-1)}\,(N↑2T↓0-NT↓1+T↓2)\,.$$

The variance can also be expressed as a multiple of 
$S=\sum (U↓{ab}-U↓{db})(U↓{ab}-U↓{ae})$, which for 0--1 valued $U$ is the
number of ways of selecting a value~$U↓{ab}$, a~distinct value $U↓{db}$
in the same column, and a distinct value $U↓{ae}$
in the same row; for obvious
reasons, I~call the summand the $L$-shaped function. One readily finds
$S=N↑2T↓0-NT↓1+T↓2$, so $V=S/\bigl(N↑2(N-1)\bigr)$. The clue to the
significance of $S$ is that both $V$ and the $L$-shaped summand of $S$
vanish if $U↓{ij}$ is independent of one subscript.

We can also express $V$ as a function of
$$(U↓{ab}-{\rm average\ of\ row\ }a)\times (U↓{ab}-
{\rm average\ of\ column\ }b)\,.$$
Let
$$\eqalignno{T&=\sum↓{ab}(NU↓{ab}-U↓{a\ast})(NU↓{ab}-U↓{\ast b})\cr
&=N↑2T↓0-NT↓1+T↓2\,;\quad T=S\,,\cr
\noalign{\hbox{and}}
V&={T\over N↑2(N-1)}\,.\cr}$$
We apply the above theory to a stratified experiment in backgammon
to determine the maxmum probability of bearing off in two rolls with
checkers on the 2, 3, 4,~5 points. In the table below, first and second
rolls are grouped in equivalence classes and their multiplicities are shown.
Row sums $U↓{a\ast}$ are shown in the right margin, column sums $U↓{\ast b}$
at the bottom.

$$\vbox{\tabskip=0pt\offinterlineskip
\halign{\lft{#}\quad&\rt{#}\quad&\vrule#&\strut\quad\rt{#}\quad
&\rt{#}\quad&\rt{#}\quad&\rt{#}\quad&\rt{#}\quad&\rt{#}\quad&\rt{#}\quad%
&\rt{#}\quad&\rt{#}\quad&\rt{#}\quad&\vrule#&\quad\ctr{#}\cr
First&Multi-&\omit&\multispan{10}\hfil Second Rolls\hfil&\omit&Row\cr
\noalign{\smallskip}
Rolls&plicity&\omit&&&&&&&&&&&\omit&sum\cr
&&\omit&4&6&4&1&4&2&2&2&\phantom{0}4&\phantom{0}7\cr
&&\multispan{12}\hrulefill\cr
&&height 2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&&\omit\cr
66,55,44,33&4&&1&1&1&1&1&1&1&1&1&1&&\phantom{0}36\cr
65,64,54&6&&1&1&1&1&1&1&1&1&&&&\phantom{0}25\cr
63,53&4&&1&1&1&1&1&1&1&&&&&\phantom{0}23\cr
22&1&&1&1&1&1&1&&&&1&&&\phantom{0}23\cr
62,52&4&&1&1&1&1&&1&&&&&&\phantom{0}17\cr
43&2&&1&1&1&1&1&&&&&&&\phantom{0}19\cr
42&2&&1&1&1&&&&&&&&&\phantom{0}14\cr
32&2&&1&1&&&&&&&&&&\phantom{0}10\cr
61,51&4&&1&&&1&&&&&&&&\phantom{00}5\cr
41,31,21,11&7&&1&&&&&&&&&&&\phantom{00}4\cr
&&\multispan{13}\hrulefill\cr
&&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit%
&\omit&height2pt&\omit\cr
&&\omit&36&25&23&25&17&18&14&10&5&4&&611\cr}}$$

\smallskip

$$\eqalign{\sum U↓{a\ast}↑2&=14261\,,\qquad \sum U↓{\ast b}↑2=14283\,,\qquad
U↓{\ast\ast}=611\,,\cr
T↓0&=611\,,\qquad T↓1=28544\,,\qquad T↓2=373321\,,\cr
V&={137593\over 36↑2\cdot 35}=3.0333554\,.\cr}$$
For comparison, using unstratified sampling 36 times, the number of successes
has variance
$$611(1296-611)/36↑3=8.9706576\,$$ 
almost three times as great. An experiment
of over 100~samplings would be required to estimate $U↓{\ast\ast}$ with
the same accuracy.

This shows the value, at least for two-roll positions, of experimenting
by using every first roll once, in fixed order, and letting each later
roll be obtained by random permutation of the 36 possible rolls.

The corresponding method for sampling the $N\times N\times N$ cube, 
corresponding to three-roll backgammon positions, sums
$\{U↓{i\,p(i)q(i)}\}$ or
$\{U↓{p(i)q(i)r(i)}\}$, where $p$, $q$, and~$r$ are random permutations.
The analogous basis functions for quadratic forms with the right symmetry are:
$$\eqalign{T↓0&=\sum U↓{abc}↑2\cr
T↓1&=\sum U↓{ab\ast}↑2+\sum U↓{a\ast c}↑2+\sum U↓{\ast bc}↑2\cr
T↓2&=\sum U↓{a\ast\ast}↑2+\sum U↓{\ast b\ast}↑2+\sum U↓{\ast\ast c}↑2\cr
T↓3&=U↓{\ast\ast\ast}↑2\,.\cr}$$
The analogous set of cases for which it is easy to evaluate $V$, $T↓0$,
$T↓1$, $T↓2$, $T↓3$~as:

$$\vcenter{\halign{$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\lft{#}$\qquad&
$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\lft{#}$\cr
\hbox{Case}&V&T↓0&T↓1&T↓2&T↓3\cr
\noalign{\smallskip}
F↓0&{N↑2-1\over N↑4}&1&3&3&1\cr
F↓1&{N-1\over N↑2}&N&N↑2+2N&2N↑2+N&N↑2\cr
F↓2&0&N↑2&2N↑3+N↑2&N↑4+2N↑3&N↑4\cr
F↓3&0&N↑3&3N↑4&3N↑5&N↑6\cr}}$$

We find
$$V={-1\over N↑2(N-1)↑2}\,(T↓0-T↓1+T↓2-T↓3)+{T↓0\over N↑2}-{T↓3\over N↑4}$$
which probably generalizes to sampling ``cubes'' of dimension greater than
three.

Applying this result to the case where $U↓{bc}=1$ only when $a≤A$,
$b≤B$, $c≤C$, we find
$$\eqalign{T↓0&=ABC\,,\cr 
T↓1&=ABC(A+B+C)\,,\cr
T↓2&=ABC(AB+AC+BC)\,,\cr
T↓3&=A↑2B↑2C↑2\,,\cr
V&={A(A-1)B(B-1)C(C-1)\over N↑2(N-1)↑2}+{ABC\over N↑2}-{A↑2B↑2C↑2\over N↑4}\,;\cr}$$
if $A=B=C=N/2$, 
$$V={4N↑3-5N↑2\over 64(N-1)↑2}\,,$$ 
asymptotically $\sim N/16$,
where unstratified sampling gives a variance of~$7N/64$.

Specializing to two dimensions by letting $C=N$, we get
$$V={A(A-1)B(B-1)\over N(N-1)}+{AB\over N}-{A↑2B↑2\over N↑2}
={AB(N-A)(N-B)\over N↑2(N-1)}\,;$$ 
for fixed~$N$, this is maximized at
$A=B=N/2$, with a variance of 
$${N↑2\over 16(N-1)}\sim {N\over 16}\,;$$
unstratified sampling has variance~$3N/16$.

Some quadratic forms related to $V$ which vanish on $F↓2$ and $F↓3$ are:
$$\vcenter{\halign{$\ctr{#}\;$&$\;#\;$&$\lft{#}$\cr
S=&&\sum (U↓{abc}-U↓{abf})(U↓{def}-U↓{abf})\cr
&+&\sum (U↓{abc}-U↓{aec})(U↓{def}-U↓{aec})\cr
&+&\sum (U↓{abc}-U↓{dbc})(U↓{def}-U↓{dbc})\,.\cr}}$$

$$\eqalign{S(F↓0)&=3(N-1)(N↑2-1)\cr
S(F↓1)&=2N↑2(N-1)↑2\,.\cr}$$

$$\vcenter{\halign{$\ctr{#}\;$&$\;#\;$&$\lft{#}$\cr
X=&&\sum (U↓{abc}-U↓{dbc})(U↓{abc}-U↓{aec})\cr
&+&\sum (U↓{abc}-U↓{dbc})(U↓{abc}-U↓{abf})\cr
&+&\sum (U↓{abc}-U↓{aec})(U↓{abc}-U↓{abf})\,.\cr}}$$

$$\eqalign{X(F↓0)&=3(N-1)↑2\cr
X(F↓1)&=N(N-1)↑2\,.\cr}$$

Clearly, $V$ must be a linear combination of $S$ and~$X$. It is in
fact ${(2N-1)S-N(N+1)X\over 3N↑4(N-1)↑2}$, which does not suggest anything.

Restricting the subscripts in $S$ to $a≠d$, $b≠e$, $c≠f$, we get
$$\eqalign{S'(F↓0)&=3(N-1)↑3\cr
S'(F↓1)&=2N(N-1)↑3\,,\cr}$$
but $V$ as a linear combination of $S'$ and~$X$ is worse than ever.

If $N=2$, the cube is 

\figbox 2truein:

\noindent and the variance is proportional to $(\alpha -\beta)↑2+\cdots
+(\gamma -\delta)↑2$ where $\alpha =A+a$, $\beta =B+b$, etc.; 
$$\vcenter{\halign{$\rt{#}\;$&$\lft{#}$\qquad&\lft{#}\cr
16V&=3(A↑2+B↑2+\cdots +d↑2)\cr
&\qquad\null+6(Aa+\cdots +Dd)&(all opposite pairs)\cr
&\qquad\null-2(AB+\cdots +cd)&(all non-opposite pairs)\cr}}$$
Let's try to generalize this to
$$\eqalign{&3\sum U↓{abc}↑2-(?)\biggl(\,\sum↓{a≠d}U↓{abc}U↓{dbc}+{\rm symmetries})
\biggr)\cr
\noalign{\smallskip}
&\quad\null+(?)\biggl(\,\sum↓{{\scriptstyle a≠d\atop \scriptstyle b≠e}\atop
\scriptstyle c≠f}U↓{abc}U↓{def}\biggr)-(?)
\biggl(\,\sum↓{\scriptstyle a≠d\atop \scriptstyle b≠e}U↓{abc}U↓{dec}\ldots\biggr)\cr
}$$

\vfill\eject\end